// Go作者版权所有。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

package ssa

// Shortcircuit查找分支方向
// 始终关联并重写CFG以获取
// 这一事实的好处。
// 此优化对于编译&&和| |表达式非常有用。
func shortcircuit(f *Func) {
	// 步骤1：如果phi arg为常数，则将其替换为常数
	// 前一个If块的控制值。
	// b1：
	// 如果转到b2或b3
	// b2:<-b1。。。
	// x=φ（a，…）
	// None
	// 我们可以用常数true替换φ中的“a”。
	var ct, cf *Value
	for _, b := range f.Blocks {
		for _, v := range b.Values {
			if v.Op != OpPhi {
				continue
			}
			if !v.Type.IsBoolean() {
				continue
			}
			for i, a := range v.Args {
				e := b.Preds[i]
				p := e.b
				if p.Kind != BlockIf {
					continue
				}
				if p.Controls[0] != a {
					continue
				}
				if e.i == 0 {
					if ct == nil {
						ct = f.ConstBool(f.Config.Types.Bool, true)
					}
					v.SetArg(i, ct)
				} else {
					if cf == nil {
						cf = f.ConstBool(f.Config.Types.Bool, false)
					}
					v.SetArg(i, cf)
				}
			}
		}
	}

	// 步骤2：围绕已知分支重定向控制流。
	// p:
	// ... 转到b。。。
	// b:<-p。。。
	// v=φ（真，…）
	// 如果你去了其他地方
	// 我们可以将p重定向到t而不是b。
	// （如果v在b之后不带电）。
	fuse(f, fuseTypePlain|fuseTypeShortCircuit)
}

// shortcircuitBlock检查其中包含If块的CFG
// 将具有ConstBool arg的Phi作为其控制值。
// 在某些情况下，我们可以将CFG重写为更平坦的形式。
// None
// （1） 查找表单的CFG
// None
// p其他预测数据
// \ /
// B
// / \
// 其他成功
// None
// 其中，b是一个If块，包含一个phi值和一次使用（b的控制），
// 它有一个ConstBool参数。
// p是与在其中找到ConstBool的参数槽相对应的前置项。
// t是与ConstBool arg的值相对应的后继值。
// None
// 把这个改写成
// None
// p其他预测数据
// |  /
// |b
// |/ \
// TU
// None
// 并移除相应的phi arg。
// None
// （2） 查找表单的CFG
// None
// p q
// \ /
// B
// / \
// TU
// None
// 其中b如（1）所述。
// 然而，b也可以包含其他φ值。
// CFG将按照（1）中所述进行修改。
// 但是，为了处理这些其他φ值，
// 对于其他φ值w，我们必须能够从b中消除w。
// 我们可以通过将w移动到不同的块来实现这一点
// 重写使用w来使用不同的值。
// 有关详细信息，请参阅shortcircuitPhiPlan。
func shortcircuitBlock(b *Block) bool {
	if b.Kind != BlockIf {
		return false
	}
	// 查找表单Copy的控制值（Not（Copy（Phi（const，…）））。
	// 这些值必须是b中唯一的值，并且每个值只能由b使用。
	// 跟踪否定，以便我们以后可以根据需要交换后续项。
	ctl := b.Controls[0]
	nval := 1 // 控制值
	var swap int64
	for ctl.Uses == 1 && ctl.Block == b && (ctl.Op == OpCopy || ctl.Op == OpNot) {
		if ctl.Op == OpNot {
			swap = 1 ^ swap
		}
		ctl = ctl.Args[0]
		nval++ // 包装控制值
	}
	if ctl.Op != OpPhi || ctl.Block != b || ctl.Uses != 1 {
		return false
	}
	nOtherPhi := 0
	for _, w := range b.Values {
		if w.Op == OpPhi && w != ctl {
			nOtherPhi++
		}
	}
	if nOtherPhi > 0 && len(b.Preds) != 2 {
		// 我们依赖于b在短路计划中正好有两个pred
		// 对潜在危险装置的价值进行推理。
		return false
	}
	if len(b.Values) != nval+nOtherPhi {
		return false
	}
	if nOtherPhi > 0 {
		// 检查作为另一个phi参数的任何phi。
		// 这些情况很棘手，因为替换是由替换者进行的
		// 在任何排序中都不再是琐碎的事情。见第45175期。
		m := make(map[*Value]bool, 1+nOtherPhi)
		for _, v := range b.Values {
			if v.Op == OpPhi {
				m[v] = true
			}
		}
		for v := range m {
			for _, a := range v.Args {
				if a != v && m[a] {
					return false
				}
			}
		}
	}

	// 找到第一个常量phi arg的索引。
	cidx := -1
	for i, a := range ctl.Args {
		if a.Op == OpConstBool {
			cidx = i
			break
		}
	}
	if cidx == -1 {
		return false
	}

	// p是对应于cidx的前置。
	pe := b.Preds[cidx]
	p := pe.b
	pi := pe.i

	// t是“take”分支：我们从p进入时总是去寻找的继任者。
	ti := 1 ^ ctl.Args[cidx].AuxInt ^ swap
	te := b.Succs[ti]
	t := te.b
	if p == b || t == b {
		// 这是一个无限循环；我们不能移除它。见第33903期。
		return false
	}

	var fixPhi func(*Value, int)
	if nOtherPhi > 0 {
		fixPhi = shortcircuitPhiPlan(b, ctl, cidx, ti)
		if fixPhi == nil {
			return false
		}
	}

	// 我们承诺了。更新CFG和Phis。
	// 如果修改此部分，请更新相应的shortcircuitPhiPlan。

	// 从p移除b的输入边。
	b.removePred(cidx)
	n := len(b.Preds)
	ctl.Args[cidx].Uses--
	ctl.Args[cidx] = ctl.Args[n]
	ctl.Args[n] = nil
	ctl.Args = ctl.Args[:n]

	// 将p的输出边重定向到t。
	p.Succs[pi] = Edge{t, len(t.Preds)}

	// 修复t，使其具有一个以上的前置程序。
	t.Preds = append(t.Preds, Edge{p, pi})
	for _, v := range t.Values {
		if v.Op != OpPhi {
			continue
		}
		v.AddArg(v.Args[te.i])
	}

	if nOtherPhi != 0 {
		// 根据需要调整所有其他潜在危险装置。
		// 使用普通for循环代替range，因为fixPhi可能会移动phi，
		// 因此，修改b值。
		for i := 0; i < len(b.Values); i++ {
			phi := b.Values[i]
			if phi.Uses == 0 || phi == ctl || phi.Op != OpPhi {
				continue
			}
			fixPhi(phi, i)
			if phi.Block == b {
				continue
			}
			// phi和v.moveTo被转移到了另一个街区。
			// 调整此新块中参考的phi值
			// 改为参考相应的phi参数。
			// phi在该块之前进行评估，
			// 现在在这个模块中进行评估。
			for _, v := range phi.Block.Values {
				if v.Op != OpPhi || v == phi {
					continue
				}
				for j, a := range v.Args {
					if a == phi {
						v.SetArg(j, phi.Args[j])
					}
				}
			}
			if phi.Uses != 0 {
				phielimValue(phi)
			} else {
				phi.reset(OpInvalid)
			}
			i-- // v、 移动以在索引i处放置新值；再加工
		}

		// 我们可能留下了一些没有用处的φ值
		// 但争论的数量是错误的。消除这些。
		for _, v := range b.Values {
			if v.Uses == 0 {
				v.reset(OpInvalid)
			}
		}
	}

	if len(b.Preds) == 0 {
		// 布洛克现在死了。
		b.Kind = BlockInvalid
	}

	phielimValue(ctl)
	return true
}

// shortcircuitPhiPlan返回一个函数来处理b中的非ctl phi值，
// 其中，b如短路块中所述。
// 返回的函数接受一个值v
// v.Block中v的索引i:v.Block.Values[i]==v。
// 如果返回的函数是movev，则它将使用movev。
// cidx是ConstBool参数的ctl中的索引。
// ti是b中的索引。当从p到达时，始终执行的分支的成功率。
// 如果shortcircuitPhiPlan返回nil，则没有可用的计划，
// 不得进行CFG修改。
// 返回的函数假定shortcircuitBlock已完成其CFG修改。
func shortcircuitPhiPlan(b *Block, ctl *Value, cidx int, ti int64) func(*Value, int) {
	// t是“take”分支：我们从p进入时总是去寻找的继任者。
	t := b.Succs[ti].b
	// u是“未被挖掘”的分支：我们从p进来时永远不会去寻找的继任者。
	u := b.Succs[1^ti].b

	// 在下面的CFG匹配中，确保b的pred与b的succs完全不同。
	// 这可能是一个比要求更强的条件，但这种情况很少发生，
	// 而且它更容易避免被漂亮的ASCII图表欺骗。见#44465。
	if p0, p1 := b.Preds[0].b, b.Preds[1].b; p0 == t || p1 == t || p0 == u || p1 == u {
		return nil
	}

	// 寻找一些常见的CFG结构
	// 其中来自b的出站路径合并，
	// 没有其他pred加入他们。
	// 在这些情况下，我们可以重建
	// b中任何φ的值必须在后续块中。

	if len(t.Preds) == 1 && len(t.Succs) == 1 &&
		len(u.Preds) == 1 && len(u.Succs) == 1 &&
		t.Succs[0].b == u.Succs[0].b && len(t.Succs[0].b.Preds) == 2 {
		// p q
		// \ /
		// B
		// / \
		// TU
		// \ /
		// M
		// None
		// 在CFG修改之后，这看起来像
		// None
		// p q
		// |  /
		// |b
		// |/ \
		// TU
		// \ /
		// M
		// None
		// 注意：t.Preds是（b，p），而不是（p，b）。
		m := t.Succs[0].b
		return func(v *Value, i int) {
			// 用v必须具有的值替换t和u中v的任何用途，
			// 既然我们已经到了那个街区。
			// 然后将v移动到m并相应地调整其值；
			// 这将处理v的所有其他用途。
			argP, argQ := v.Args[cidx], v.Args[1^cidx]
			u.replaceUses(v, argQ)
			phi := t.Func.newValue(OpPhi, v.Type, t, v.Pos)
			phi.AddArg2(argQ, argP)
			t.replaceUses(v, phi)
			if v.Uses == 0 {
				return
			}
			v.moveTo(m, i)
			// m中的φ属于与t相对应的pred idx。
			if m.Preds[0].b == t {
				v.SetArgs2(phi, argQ)
			} else {
				v.SetArgs2(argQ, phi)
			}
		}
	}

	if len(t.Preds) == 2 && len(u.Preds) == 1 && len(u.Succs) == 1 && u.Succs[0].b == t {
		// p q
		// \ /
		// B
		// |\
		// |u
		// |/
		// T
		// None
		// 在CFG修改之后，这看起来像
		// None
		// Q
		// /
		// B
		// |\
		// p|u
		// \|/
		// T
		// None
		// 注：t.Preds是（b或u，b或u，p）。
		return func(v *Value, i int) {
			// 在u中替换v的任何用法。然后把v移到t。
			argP, argQ := v.Args[cidx], v.Args[1^cidx]
			u.replaceUses(v, argQ)
			v.moveTo(t, i)
			v.SetArgs3(argQ, argQ, argP)
		}
	}

	if len(u.Preds) == 2 && len(t.Preds) == 1 && len(t.Succs) == 1 && t.Succs[0].b == u {
		// p q
		// \ /
		// B
		// /|
		// t|
		// \|
		// U
		// None
		// 在CFG修改之后，这看起来像
		// None
		// p q
		// |  /
		// |b
		// |/|
		// t|
		// \|
		// U
		// None
		// 注意：t.Preds是（b，p），而不是（p，b）。
		return func(v *Value, i int) {
			// 替换t中v的任何用途。然后把v移到u。
			argP, argQ := v.Args[cidx], v.Args[1^cidx]
			phi := t.Func.newValue(OpPhi, v.Type, t, v.Pos)
			phi.AddArg2(argQ, argP)
			t.replaceUses(v, phi)
			if v.Uses == 0 {
				return
			}
			v.moveTo(u, i)
			v.SetArgs2(argQ, phi)
		}
	}

	// 寻找一些常见的CFG结构
	// 其中一条来自b的出站路径退出，
	// 没有其他pred加入。
	// 在这些情况下，我们可以重建
	// b中任何φ的值必须位于通向出口的路径中，
	// 并将phi移动到非出口路径。

	if len(t.Preds) == 1 && len(u.Preds) == 1 && len(t.Succs) == 0 {
		// p q
		// \ /
		// B
		// / \
		// TU
		// None
		// 其中t为出口/出口闭塞。
		// None
		// 在CFG修改之后，这看起来像
		// None
		// p q
		// |  /
		// |b
		// |/ \
		// TU
		// None
		// 注意：t.Preds是（b，p），而不是（p，b）。
		return func(v *Value, i int) {
			// 替换t和x中v的任何用途。然后把v移到u。
			argP, argQ := v.Args[cidx], v.Args[1^cidx]
			// 如果t或x中没有v的使用，则该phi将不使用。
			// 没关系；不值得为此付出代价。
			phi := t.Func.newValue(OpPhi, v.Type, t, v.Pos)
			phi.AddArg2(argQ, argP)
			t.replaceUses(v, phi)
			if v.Uses == 0 {
				return
			}
			v.moveTo(u, i)
			v.SetArgs1(argQ)
		}
	}

	if len(u.Preds) == 1 && len(t.Preds) == 1 && len(u.Succs) == 0 {
		// p q
		// \ /
		// B
		// / \
		// TU
		// None
		// 其中，u是一个出口/出口块。
		// None
		// 在CFG修改之后，这看起来像
		// None
		// p q
		// |  /
		// |b
		// |/ \
		// TU
		// None
		// 注意：t.Preds是（b，p），而不是（p，b）。
		return func(v *Value, i int) {
			// 替换u（和x）中v的任何用法。然后把v移到t。
			argP, argQ := v.Args[cidx], v.Args[1^cidx]
			u.replaceUses(v, argQ)
			v.moveTo(t, i)
			v.SetArgs2(argQ, argP)
		}
	}

	// 待办事项：处理更多案件；结果证明，短路优化具有相当高的影响
	return nil
}

// replaceUses用new替换b中的所有旧用法。
func (b *Block) replaceUses(old, new *Value) {
	for _, v := range b.Values {
		for i, a := range v.Args {
			if a == old {
				v.SetArg(i, new)
			}
		}
	}
	for i, v := range b.ControlValues() {
		if v == old {
			b.ReplaceControl(i, new)
		}
	}
}

// moveTo将v移动到dst，调整适当的块值。
// 呼叫方负责确保这是安全的。
// i是v.Block.Values中v的索引。
func (v *Value) moveTo(dst *Block, i int) {
	if dst.Func.scheduled {
		v.Fatalf("moveTo after scheduling")
	}
	src := v.Block
	if src.Values[i] != v {
		v.Fatalf("moveTo bad index %d", v, i)
	}
	if src == dst {
		return
	}
	v.Block = dst
	dst.Values = append(dst.Values, v)
	last := len(src.Values) - 1
	src.Values[i] = src.Values[last]
	src.Values[last] = nil
	src.Values = src.Values[:last]
}
